using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace CMSWeb.Utility.Difference
{
	public class Diff<T> where T : IEquatable<T>
	{

		public Diff(T[] dataA, T[] dataB)
		{
			_dataSource = new DiffData<T>(dataA);
			_dataDestination = new DiffData<T>(dataB);

			Init();
		}

		public Diff(IEnumerable<T> dataA, IEnumerable<T> dataB)
		{
			_dataSource = new DiffData<T>(GetArray(dataA));
			_dataDestination = new DiffData<T>(GetArray(dataB));

			Init();
		}

		protected void Init()
		{
			MAX = _dataSource.Length + _dataDestination.Length + 1;
			/// vector for the (0,0) to (x,y) search
			downVector = new int[2 * MAX + 2];

			/// vector for the (u,v) to (N,M) search
			upVector = new int[2 * MAX + 2];
		}

		public DiffItem[] GetChanges()
		{
			// actually run the diff here
			LCS(0, _dataSource.Length, 0, _dataDestination.Length);

			List<DiffItem> items = new List<DiffItem>();
			DiffItem item;

			int startSource, startDestination;
			int lineSource, lineDestination;

			lineSource = 0;
			lineDestination = 0;
			while ( lineSource < _dataSource.Length || lineDestination < _dataDestination.Length )
			{
				if ( 
					( lineSource < _dataSource.Length ) && 
					( !_dataSource.Modified[lineSource] ) && 
					( lineDestination < _dataDestination.Length ) && 
					( !_dataDestination.Modified[lineDestination] ) 
					)
				{
					// equal lines
					lineSource++;
					lineDestination++;

				}
				else
				{
					// maybe deleted and/or inserted lines
					startSource = lineSource;
					startDestination = lineDestination;

					// while (LineA < DataA.Length && DataA.modified[LineA])
					while ( lineSource < _dataSource.Length && ( lineDestination >= _dataDestination.Length || _dataSource.Modified[lineSource] ) )
						lineSource++;

					// while (LineB < DataB.Length && DataB.modified[LineB])
					while ( lineDestination < _dataDestination.Length && ( lineSource >= _dataSource.Length || _dataDestination.Modified[lineDestination] ) )
						lineDestination++;

					if ( ( startSource < lineSource ) || ( startDestination < lineDestination ) )
					{
						// store a new difference-item
						item = new DiffItem();
						item.StartSource = startSource;
						item.StartDestination = startDestination;
						item.DeletedSource = lineSource - startSource;
						item.InsertedDestination = lineDestination - startDestination;
						items.Add(item);
					}
				}
			}

			return ( items.ToArray() );
		}

		protected T[] GetArray(IEnumerable<T> data)
		{
			IEnumerator<T> enm = data.GetEnumerator();
			List<T> list = new List<T>();

			while ( enm.MoveNext() )
			{
				list.Add(enm.Current);
			}

			return list.ToArray();
		}

		protected DiffData<T> _dataSource;
		protected DiffData<T> _dataDestination;

		protected int MAX = 0;

		/// vector for the (0,0) to (x,y) search
		protected int[] downVector;

		/// vector for the (u,v) to (N,M) search
		protected int[] upVector;


		/// <summary>
		/// This is the divide-and-conquer implementation of the longes common-subsequence (LCS) 
		/// algorithm.
		/// The published algorithm passes recursively parts of the A and B sequences.
		/// To avoid copying these arrays the lower and upper bounds are passed while the sequences stay constant.
		/// </summary>
		/// <param name="DataA">sequence A</param>
		/// <param name="LowerA">lower bound of the actual range in DataA</param>
		/// <param name="UpperA">upper bound of the actual range in DataA (exclusive)</param>
		/// <param name="DataB">sequence B</param>
		/// <param name="LowerB">lower bound of the actual range in DataB</param>
		/// <param name="UpperB">upper bound of the actual range in DataB (exclusive)</param>
		protected void LCS(int lowerSource, int upperSource, int lowerDestination, int upperDestination)
		{
			// Fast walkthrough equal lines at the start
			while ( lowerSource < upperSource && lowerDestination < upperDestination && _dataSource.Data[lowerSource].Equals(_dataDestination.Data[lowerDestination]) )
			{
				lowerSource++; lowerDestination++;
			}

			// Fast walkthrough equal lines at the end
			while ( lowerSource < upperSource && lowerDestination < upperDestination && _dataSource.Data[upperSource - 1].Equals(_dataDestination.Data[upperDestination - 1]) )
			{
				--upperSource; --upperDestination;
			}

			if ( lowerSource == upperSource )
			{
				// mark as inserted lines.
				while ( lowerDestination < upperDestination )
					_dataDestination.Modified[lowerDestination++] = true;

			}
			else if ( lowerDestination == upperDestination )
			{
				// mark as deleted lines.
				while ( lowerSource < upperSource )
					_dataSource.Modified[lowerSource++] = true;

			}
			else
			{
				// Find the middle snakea and length of an optimal path for A and B
				Point smsrd = SMS(lowerSource, upperSource, lowerDestination, upperDestination);
				// Debug.Write(2, "MiddleSnakeData", String.Format("{0},{1}", smsrd.x, smsrd.y));

				// The path is from LowerX to (x,y) and (x,y) ot UpperX
				LCS(lowerSource, smsrd.X, lowerDestination, smsrd.Y);
				LCS(smsrd.X, upperSource, smsrd.Y, upperDestination);  // 2002.09.20: no need for 2 points 
			}
		}

		/// <summary>
		/// This is the algorithm to find the Shortest Middle Snake (SMS).
		/// </summary>
		/// <param name="DataA">sequence A</param>
		/// <param name="LowerA">lower bound of the actual range in DataA</param>
		/// <param name="UpperA">upper bound of the actual range in DataA (exclusive)</param>
		/// <param name="DataB">sequence B</param>
		/// <param name="LowerB">lower bound of the actual range in DataB</param>
		/// <param name="UpperB">upper bound of the actual range in DataB (exclusive)</param>
		/// <returns>a MiddleSnakeData record containing x,y and u,v</returns>
		protected Point SMS(int lowerSource, int upperSource, int lowerDestination, int upperDestination)
		{
			Point ret = new Point();

			int downK = lowerSource - lowerDestination; // the k-line to start the forward search
			int upK = upperSource - upperDestination; // the k-line to start the reverse search

			int delta = ( upperSource - lowerSource ) - ( upperDestination - lowerDestination );
			bool oddDelta = ( delta & 1 ) != 0;

			// The vectors in the publication accepts negative indexes. the vectors implemented here are 0-based
			// and are access using a specific offset: UpOffset UpVector and DownOffset for DownVektor
			int downOffset = MAX - downK;
			int upOffset = MAX - upK;

			int maxD = ( ( upperSource - lowerSource + upperDestination - lowerDestination ) / 2 ) + 1;

			// init vectors
			downVector[downOffset + downK + 1] = lowerSource;
			upVector[upOffset + upK - 1] = upperSource;

			for ( int D = 0; D <= maxD; D++ )
			{

				// Extend the forward path.
				for ( int k = downK - D; k <= downK + D; k += 2 )
				{
					// Debug.Write(0, "SMS", "extend forward path " + k.ToString());

					// find the only or better starting point
					int x, y;
					if ( k == downK - D )
					{
						x = downVector[downOffset + k + 1]; // down
					}
					else
					{
						x = downVector[downOffset + k - 1] + 1; // a step to the right
						if ( ( k < downK + D ) && ( downVector[downOffset + k + 1] >= x ) )
							x = downVector[downOffset + k + 1]; // down
					}
					y = x - k;

					// find the end of the furthest reaching forward D-path in diagonal k.
					while ( 
						( x < upperSource ) && 
						( y < upperDestination ) && 
						( _dataSource.Data[x].Equals(_dataDestination.Data[y]) ) 
						)
					{
						x++; y++;
					}
					downVector[downOffset + k] = x;

					// overlap ?
					if ( oddDelta && ( upK - D < k ) && ( k < upK + D ) )
					{
						if ( upVector[upOffset + k] <= downVector[downOffset + k] )
						{
							ret.X = downVector[downOffset + k];
							ret.Y = downVector[downOffset + k] - k;
							// ret.u = UpVector[UpOffset + k];      // 2002.09.20: no need for 2 points 
							// ret.v = UpVector[UpOffset + k] - k;
							return ( ret );
						}
					}

				}

				// Extend the reverse path.
				for ( int k = upK - D; k <= upK + D; k += 2 )
				{
					// Debug.Write(0, "SMS", "extend reverse path " + k.ToString());

					// find the only or better starting point
					int x, y;
					if ( k == upK + D )
					{
						x = upVector[upOffset + k - 1]; // up
					}
					else
					{
						x = upVector[upOffset + k + 1] - 1; // left
						if ( ( k > upK - D ) && ( upVector[upOffset + k - 1] < x ) )
							x = upVector[upOffset + k - 1]; // up
					}
					y = x - k;

					while ( 
						( x > lowerSource ) && 
						( y > lowerDestination ) && 
						( _dataSource.Data[x - 1].Equals(_dataDestination.Data[y - 1]) ) 
						)
					{
						x--; y--; // diagonal
					}
					upVector[upOffset + k] = x;

					// overlap ?
					if ( !oddDelta && ( downK - D <= k ) && ( k <= downK + D ) )
					{
						if ( upVector[upOffset + k] <= downVector[downOffset + k] )
						{
							ret.X = downVector[downOffset + k];
							ret.Y = downVector[downOffset + k] - k;
							// ret.u = UpVector[UpOffset + k];     // 2002.09.20: no need for 2 points 
							// ret.v = UpVector[UpOffset + k] - k;
							return ( ret );
						}
					}

				}

			}

			throw new ApplicationException("The algorithm should never come here.");
		}
	}
}
